public class Solution {
    //定义一个成员变量 存储上一个节点的地址
    TreeNode prev;//初始值为null
 
    public void ConvertNode(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return;
        //中序遍历思想递归
        ConvertNode(pRootOfTree.left);
        
        //修改前驱，将当前节点的left域更改为前一个节点的地址
        pRootOfTree.left = prev;
        if (prev != null) {
            //当prev不为空时，修改后继
            //将其right域修改为当前节点的地址（prev本就是当前节点的前驱）
            prev.right = pRootOfTree;
        }
        //更新prev
        prev = pRootOfTree;
 
        ConvertNode(pRootOfTree.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        ConvertNode(pRootOfTree);
 
        TreeNode head = pRootOfTree;
        //找头结点
        //转换成双向链表后，链表的头结点就在pRootOfTree的左边
        //头结点的left（前驱）为null
        while(head.left != null) {
            head = head.left;
        }
 
        return head;
    }
}